import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/19 16:42
 * @description 前缀和 + HashMap
 */
public class Solution2 {
    public static void main(String[] args) {

    }
    public int pathSum(TreeNode root, int targetSum) {
        // 此处前缀和 为 节点到跟之间的路径和
        // Map 中 key 为 前缀和，value为该前缀和的节点数量
        Map<Long, Integer> prefix = new HashMap<Long, Integer>();
        // 空路径不经过任何节点，前缀和为0
        prefix.put(0L, 1);
        return dfs(root, prefix, 0, targetSum);
    }

    public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
        if (root == null) {
            return 0;
        }

        int ret = 0;
        // 当前路径上的和
        curr += root.val;

        // 获取路径上和为cur - targetSum的路径数，如果存在，那么说明 cur - (cur - targetSm) = targetSum 成立.
        ret = prefix.getOrDefault(curr - targetSum, 0);
        //更新前缀和个数
        prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
        //进入下一层
        ret += dfs(root.left, prefix, curr, targetSum);
        ret += dfs(root.right, prefix, curr, targetSum);
        // 回到本层时，恢复状态，将当前节点的前缀和数量减一。
        prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);

        return ret;
    }
}
